package medium.number;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * <a href="https://leetcode-cn.com/problems/ugly-number-ii">264. 丑数 II</a>
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 * 示例 1：
 *   输入：n = 10
 *   输出：12
 *   解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 * 示例 2：
 *   输入：n = 1
 *   输出：1
 *   解释：1 通常被视为丑数。
 * 提示：
 *   1 <= n <= 1690
 * @author 刘学松
 * @date 2021-04-11 14:03
 */
public class 丑数II {
    public static void main(String[] args) {
        System.out.println(nthUglyNumber(10));
    }

    static List<Integer> list = new ArrayList<>(1690);
    public static int nthUglyNumber(int n) {
        // TODO
        int[] uglys = {2, 3, 5, 3, 5, 5};
        int ugly = 1;
        recursion(1, 1, 0, n);
        Collections.sort(list);
        System.out.println(list);
        return list.get(n-1);
    }

    public static void recursion(int last, int cur, int count, int n) {
        if (count < n) {
            int result = last*cur;
            list.add(result);
            switch (cur) {
                case 1:
                case 2:
                    recursion(result, 2, count+1, n);
                    recursion(result, 3, count+2, n);
                    recursion(result, 5, count+3, n);
                    break;
                case 3:
                    recursion(result, 3, count+4, n);
                    recursion(result, 5, count+5, n);
                    break;
                case 5:
                    recursion(result, 5, count+6, n);
                    break;
                default:
                    break;
            }
        }
    }
}
